package com.algorithm.base.sort;

public class QuickSort {
    private static int partition(int a[], int low, int high) {
        int prim = a[low];
        while (low < high) {
            while (low < high && a[high] > prim) {
                high--;
            }
            if (low < high) {
                a[low] = a[high];
            }
            while (low < high && a[low] < prim) {
                low++;
            }
            if (low < high) {
                a[high] = a[low];
            }
        }
        a[low] = prim;
        return low;
    }

    private static void quickSort(int a[], int low, int high) {
        if (low < high) {
            int mid = partition(a, low, high);
            quickSort(a, low, mid - 1);
            quickSort(a, mid + 1, high);
        }
    }

    public static void sortArray(int a[]) {
        quickSort(a, 0, a.length - 1);
    }
}
